package jm.algorithm.sort;

/**
 * @Description 堆排序实现
 * @date 2022/5/2 9:36
 */
public class HeapSort<T extends Comparable<T>> extends Sort<T> {

    // 记录堆元素数量
    private int heapSize;

    @Override
    protected void sort() {
        // 原地建堆
        heapSize = arr.length;
        for (int i = (heapSize >> 1) - 1 ; i >= 0; i--) {
            siftDown(i);
        }

        while (heapSize > 1){
            // 交换堆顶元素和尾部元素，并减一
            swap(0, --heapSize);
            // 0 位置元素下滤
            siftDown(0);
        }
    }

    /**
     * 下滤
     * @param index 下滤索引
     */
    private void siftDown(int index) {
        T element = arr[index];
        int half = heapSize >> 1;
        while (index < half) { // index必须是非叶子节点
            // 默认是左边跟父节点比
            int childIndex = (index << 1) + 1;
            T child = arr[childIndex];
            int rightIndex = childIndex + 1;
            // 右子节点比左子节点大
            if (rightIndex < heapSize &&
                    cmp(arr[rightIndex], child) > 0) {
                child = arr[childIndex = rightIndex];
            }
            // 大于等于子节点
            if (cmp(element, child) >= 0) break;
            arr[index] = child;
            index = childIndex;
        }
        arr[index] = element;
    }
}
